import java.util.*;

public class Solution {

    /**
     * 给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
     * <p>
     * candidates中的每个数字在每个组合中只能使用一次。
     * <p>
     * 注意：解集不能包含重复的组合。
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Node> nodeList = group(candidates);
        List<List<Node>> combine = combine(nodeList, target, 0, -1);
        List<List<Integer>> separate = separate(combine);
        return separate;
    }

    public static List<List<Node>> combine(List<Node> candidates, int target, int base, int preIdx) {
        List<List<Node>> result = null;
        for (int i = preIdx + 1; i < candidates.size(); i++) {
            Node curNode = candidates.get(i);
            for (int c = 1; c <= curNode.size; c++) {
                int sum = base + (curNode.value * c);
                if (sum < target) {
                    List<List<Node>> subResult = combine(candidates, target, sum, i);
                    if (Objects.nonNull(subResult)) {
                        Node r = new Node(curNode.value, c);
                        subResult.forEach(e -> e.add(0, r));
                        if (Objects.isNull(result)) {
                            result = subResult;
                        } else {
                            result.addAll(subResult);
                        }
                    }
                } else if (sum == target) {
                    if (Objects.isNull(result)) {
                        result = new ArrayList<>();
                    }
                    List<Node> list = new ArrayList<>();
                    list.add(new Node(curNode.value, c));
                    result.add(list);
                }else {
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] candidates = new int[]{10,1,2,7,6,1,5};
        System.out.println(combinationSum2(candidates, 8));
    }

    private static List<Node> group(int[] candidates) {
        List<Node> result = new ArrayList<>();
        Map<Integer, Node> map = new HashMap<>();
        for (int c : candidates) {
            if (map.containsKey(c)) {
                map.get(c).incr();
            } else {
                Node node = new Node(c, 1);
                map.put(c, node);
                result.add(node);
            }
        }
        return result;
    }

    private static List<List<Integer>> separate(List<List<Node>> srcList){
        List<List<Integer>> result =new ArrayList<>();
        if (Objects.isNull(srcList) || srcList.isEmpty()){
            return Collections.emptyList();
        }
        for (List<Node> src : srcList){
            List<Integer> r = new ArrayList<>();
            for (Node node : src){
                int value = node.value;
                for (int i=1; i<=node.size; i++){
                    r.add(value);
                }
            }
            result.add(r);
        }
        return result;
    }

    public static class Node {
        private final int value;
        private int size = 0;

        public Node(int value, int size) {
            this.value = value;
            this.size = size;
        }

        public void incr() {
            size++;
        }
    }

}